翻訳と辞書 Words near each other ・ Graphic facilitation ・ Graphic Imaging Technology ・ Graphic kit ・ Graphic matroid ・ Graph (mathematics) ・ Graph algebra ・ Graph algebra (social sciences) ・ GRAph ALigner (GRAAL) ・ Graph amalgamation ・ Graph automorphism ・ Graph bandwidth ・ Graph C*-algebra ・ Graph canonization ・ Graph center ・ Graph coloring ・ Graph coloring game ・ Graph continuous function ・ Graph cut ・ Graph cuts in computer vision ・ Graph database ・ Graph drawing ・ Graph dynamical system ・ Graph embedding ・ Graph energy ・ Graph enumeration ・ Graph equation ・ Graph factorization ・ Graph homomorphism ・ Graph isomorphism ・ Graph isomorphism problem Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Graph coloring game ： ウィキペディア英語版 Graph coloring game The graph coloring game is a mathematical game related to graph theory. Coloring game problems arose as game-theoretic versions of well-known graph coloring problems. In a coloring game, two players are using a given set of colors to construct a coloring of a graph, following specific rules depending on the game we consider. One player tries to complete successfully the coloring of the graph, when the other one tries to prevent him to achieve it. == Vertex coloring game == The vertex coloring game was introduced in 1981 by Brahms and rediscovered ten years after by Bodlaender. Its rules are as follows: # Alice and Bob are coloring the vertices of a graph ''G'' with a set ''k'' of colors. # Alice and Bob are taking turns, coloring properly a uncolored vertex (in the standard version, Alice begins). # If a vertex ''v'' is impossible to color properly (for any color, ''v'' has a neighbor colored with it), then Bob wins. # If the graph is completely colored, then Alice wins. The game chromatic number of a graph $G$, denoted by $\backslash chi\_g(G)$, is the minimum number of colors needed for Alice to win the vertex coloring game on $G$. Trivially, for every graph $G$, we have $\backslash chi(G)\; \backslash le\; \backslash chi\_g(G)\; \backslash le\; \backslash Delta(G)\; +\; 1$, where $\backslash chi(G)$ is the chromatic number of $G$ and $\backslash Delta(G)$ its maximum degree.〔With less colors than the chromatic number, there is no proper coloring of ''G'' and so Alice cannot win. With most colors than the maximum degree, there is always an available color for coloring a vertex and so Alice cannot lose.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Graph coloring game」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.